/**
 * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
 * For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
 * 
 */


// 资料：http://www.cnblogs.com/grandyang/p/4800552.html


/**
 * DP算法
 * http://blog.csdn.net/cangchen/article/details/45044811
 * @param {*} n 
 * 如果一个数x可以表示为一个任意数a加上一个平方数bｘb，
 * 也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。
 */
const numSquares = function (n) {
    while (n % 4 == 0) n /= 4;
    if (n % 8 == 7) return 4;
    let dp = [0];
    for (let i = 1; i <= n; i++) dp.push(Infinity);
    for (let i = 0; i <= n; i++) {
        for (let j = 1; ; j++) {
            if (i + j * j > n) {
                break;
            } else {
                // if(dp[i + j * j] === null) dp[i + j * j] = dp[i] + 1;
                dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
            }
        }
    }
    return dp[n];
};


// var numSquares = function (n) {
//     while (n % 4 == 0) n /= 4;
//     if (n % 8 == 7) return 4;
//     for (var a = 0; a * a <= n; ++a) {
//         var b = Math.sqrt(n - a * a);
//         if (a * a + b * b == n) {
//             return !!a + !!b;
//         }
//     }
//     return 3;
// };

console.log(numSquares(18))